package class06_堆和堆排序.test;


public class Code02_Heap {
    public static class MyMaxHeap{
        int[] heap;
        final int limit;
        int heapSize;
        public MyMaxHeap(int limit){
            heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }
        public boolean isEmpty(){
            return heapSize == 0;
        }
        public boolean isFull(){
            return heapSize == limit;
        }

        /**
         * 添加元素
         */
        public void push(int value){
            if(heapSize == limit){
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }

        /**
         * 删除最大(最小元素)
         */
        public int pop(){
            int res = heap[0];
            swap(heap, --heapSize, 0);
            heapify(heap, 0 ,heapSize);
            return res;
        }

        /**
         * 在叶节点添加元素，顺着路径调整为大根堆
         * @param arr
         * @param index
         */
        private void heapInsert(int[] arr, int index){
            while (arr[index] > arr[(index - 1) / 2]){
                swap(arr, index, (index - 1)/2);
                index = (index - 1) / 2;
            }
        }

        /**
         * 下沉
         * @param arr
         * @param index
         * @param heapSize
         */
        private void heapify(int[] arr, int index, int heapSize){
            int left = index * 2 + 1;
            while (left < heapSize){
                int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
                largest = arr[largest] > arr[index] ? largest : index;
                if(largest == index){
                    break;
                }
                swap(arr, index, largest);
                index = largest;
                left = index * 2 + 1;
            }
        }

        private static void swap(int[] arr, int a, int b) {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

        public static class RightMaxHeap{
            private int[] arr;
            private  int size;
            private final int limit;
            public RightMaxHeap(int limit){
                arr = new int[limit];
                size = 0;
                this.limit = limit;
            }
            public boolean isEmpty(){
                return size == 0;
            }
            public boolean isFull(){
                return size == limit;
            }

            public void push(int value){
                if(size == limit){
                    throw new RuntimeException("heap is full");
                }
                arr[size++] = value;
            }

            public int poll(){
                int maxIndex = 0;
                for (int i = 0; i < size; i++) {
                    if(arr[maxIndex] < arr[i]){
                        maxIndex = i;
                    }
                }
                int res = arr[maxIndex];
                swap(arr, maxIndex, --size);
//                arr[maxIndex] = arr[--size];
                return res;
            }

        }

        public static void main(String[] args) {
            int testTime = 500000;
            int limit = 100;
            int value = 1000;
            for (int i = 0; i < testTime; i++) {
                int curLimit = (int) (Math.random() * limit + 1);
                MyMaxHeap myMaxHeap = new MyMaxHeap(curLimit);
                RightMaxHeap rightMaxHeap = new RightMaxHeap(curLimit);
                int curOpTimes = (int) (Math.random() * limit);
                for (int j = 0; j < curOpTimes; j++) {
                    if (myMaxHeap.isEmpty() != rightMaxHeap.isEmpty()) {
                        System.out.println("Oops!!!");
                    }
                    if (myMaxHeap.isFull() != rightMaxHeap.isFull()) {
                        System.out.println("Oops!!!");
                    }
                    if (myMaxHeap.isEmpty()) {
                        int curValue = (int) (Math.random() * value + 1);
                        myMaxHeap.push(curValue);
                        rightMaxHeap.push(curValue);
                    } else if (myMaxHeap.isFull()) {
                        if (myMaxHeap.pop() != rightMaxHeap.poll()) {
                            System.out.println("Oops");
                        }
                    } else {
                        if (Math.random() < 0.5) {
                            int curValue = (int) (Math.random() * value + 1);
                            myMaxHeap.push(curValue);
                            rightMaxHeap.push(curValue);
                        } else {
                            if (myMaxHeap.pop() != rightMaxHeap.poll()) {
                                System.out.println("Oops");
                            }
                        }
                    }
                }
            }
            System.out.println("test end!!");
        }
    }
}
